   1	/*
   2	 * =====================================================================================
   3	 *
   4	 *       Filename:  tree23.hpp
   5	 *
   6	 *    Description:  2-3树的实现
   7	 *
   8	 *        Version:  1.0
   9	 *        Created:  2017年05月02日 21时27分48秒
  10	 *       Revision:  none
  11	 *       Compiler:  gcc
  12	 *
  13	 *         Author:  Crane (), 215379951@qq.com
  14	 *   Organization:  Free Src
  15	 *
  16	 * =====================================================================================
  17	 */
  18
  19	/* 关于C++模板使用
  20	 * 模板使用总结: 在template类中的T相关类型, 都可以被typedef.
  21	 * 比如 T类型的比较函数指针, T类型的指针等.
  22	 *
  23	 * 如果在 类外要使用T 类型指针, 比如函数中. 将函数定义为模板函数即可.
  24	 */
  25
  26	/*
  27	 * 关于2-3树说明
  28	 * 一棵树用一个Tree23_Node 类型指针表示.
  29	 * Tree23_Slot 表示2
  30	 */
  31
  32
  33	#ifndef  tree23_H_
  34	#define  tree23_H_
  35
  36	#include <iostream>
  37	#include <assert.h>
  38	#include <string.h>
  39
  40
  41	// 比较函数返回值.
  42	typedef int comp_t;
  43
  44	const int COMP_GT =  1;
  45	const int COMP_EQ =  0;
  46	const int COMP_LE = -1;
  47
  48	// 函数返回值.
  49	const int kTREE23_SUC        =  0;          // 成功
  50	const int kTREE23_ERR        = -1;          // 内部错误
  51
  52	const int kTREE23_UNKNOW_ERR = -100;        // 未错误, 比如程序流程执行到了不该执行的地方
  53
  54	const int kTREE23_EXIST      = -200;        // 插入时, key已存在
  55	const int kTREE23_MEMORY     = -201;        // 没有足够的内存可用
  56
  57
  58	// 前置声明, 在 Tree23_Slot 中要用到Tree23_Node类型的指针.
  59	template <class T>
  60	class Tree23_Node;
  61
  62	template <class T>
  63	class  Tree23_Slot;
  64
  65	template <class T>
  66	class  ExplodeNode;
  67
  68
  69	// 必须: T 类型需要重载 >, ==, < 操作符号, 还要支持拷贝构造
  70	template <class T>
  71	class  Tree23
  72	{
  73	public:
  74	    typedef Tree23_Node<T>   *PNode;        // 指向Tree23_Node 类型的指针指向Tree23_Node 类型的指针.
  75	    typedef Tree23_Node<T>    Node;
  76
  77	private:
  78	    PNode    root;
  79	    PNode newRoot;
  80
  81	public:
  82	    Tree23( ) {
  83	        root    = NULL;
  84	        newRoot = NULL;
  85	    }
  86
  87	    int Insert(T ele) {
  88	        int ret = 0;
  89	        ret = root->Insert(ele, newRoot);
  90
  91	        if (ret != kTREE23_SUC)
  92	            return ret;
  93
  94	        if ( NULL == newRoot )
  95	            return ret;
  96
  97	        root = newRoot;
  98	        newRoot = NULL;
  99
 100	        return ret;
 101	    }
 102
 103	    bool Find(T ele) {
 104	        PNode findNode;
 105	        return root->Find(ele, findNode);
 106	    }
 107
 108	    // T ele要支持遍历打印数据, 需要重载 std::cout << 操作符号.
 109	    void Traversal() {
 110	        root->Traversal();
 111	    }
 112
 113	};
 114
 115	template <class T>
 116	class Tree23_Node
 117	{
 118	public:
 119	    typedef Tree23_Node<T>   *Tree;         // 用 Tree23_Node指针类型表示2-3 树.
 120	    typedef Tree23_Node<T>   *SubTree;      // 用 Tree23_Node指针类型表示2-3子树.
 121	    typedef Tree23_Node<T>   *PNode;        // 指向Tree23_Node 类型的指针指向Tree23_Node 类型的指针.
 122	    typedef Tree23_Node<T>    Node;
 123	    typedef Tree23_Slot<T>    Slot;
 124
 125	    typedef ExplodeNode<T>    ExpNode;      // 一颗即将爆裂的节点.
 126
 127	public:
 128	    // 成员: 2个Slot元素, 三颗子树, 1个指向父节点的指针.
 129	    Slot       m_leftSlot;
 130	    Slot       m_rightSlot;
 131
 132	    SubTree m_parent;               // m_parent 父节点
 133	    SubTree m_leftTree;             // 左子树
 134	    SubTree m_midTree;              // 中子树
 135	    SubTree m_rightTree;            // 右子树
 136
 137	public:
 138	    Tree23_Node()
 139	    {
 140	        initResource();
 141	    }
 142
 143	    Tree23_Node(T leftEle) : m_leftSlot(leftEle)
 144	    {
 145	        initResource();
 146	    }
 147
 148	    Tree23_Node(T leftEle, T rightEle) : m_leftSlot(leftEle), m_rightSlot(rightEle)
 149	    {
 150	        initResource();
 151	    }
 152
 153
 154	    /*
 155	     * 先查询是否存在节点, 如果不存在, 再插入.
 156	     * 插入后, 如果树根改变, 返回修改后的树根.
 157	     * 否则传入newRoot不做修改.
 158	     */
 159	    int Insert(T ele, Tree &newRoot)
 160	    {
 161	        PNode findNode;
 162	        bool  isExist = Find(ele, findNode);
 163
 164	        if (isExist)
 165	            return kTREE23_EXIST;
 166
 167	        // 如果不存在, 那么将新生成的节点插入到 findNode中(内部可能涉及到节点的分裂和向上移动操作)
 168	        // tips: findNode, 一定位于树的最底层.
 169	        //     : new出来的节点, 就不要费心了, 由被调用者释放.
 170	        return findNode->InsertNode(new Node(ele), newRoot);
 171	    }
 172
 173	    //   找到: 返回true, 返回ele所在节点的指针
 174	    // 未找到: 返回false, 返回最终终止的节点的指针
 175	    bool Find(T ele, PNode &findNode)
 176	    {
 177	        //assert(this != NULL);           // 不要在空树上查询一个节点, 后期可能会允许, 并返回NULL
 178	        if (NULL == this)
 179	        {
 180	            findNode = NULL;
 181	            return false;
 182	        }
 183
 184	        findNode = this;
 185
 186	        if ( isEmptySlot() )
 187	            return false;
 188
 189	        // 下面是 one slot情况: 当前节点至少有一个左元素.
 190	        if ( m_leftSlot.IsEquel(ele) )
 191	            return true;
 192
 193	        if ( ele < m_leftSlot.GetEle() )
 194	            return leftFind(ele, findNode);
 195
 196	        if ( isOneSlot() )
 197	            return midFind(ele, findNode);
 198
 199	        // 下面是full slot 情况
 200	        if ( m_rightSlot.IsEquel(ele) )
 201	            return true;
 202
 203	        if ( ele > m_rightSlot.GetEle() )
 204	            return rightFind(ele, findNode);
 205
 206	        if ( ele < m_rightSlot.GetEle() )
 207	            return midFind(ele, findNode);
 208
 209	        assert(false);             // 程序逻辑正确的话, 不会执行到这里, 因为i前面将情况都列举完了.
 210	        return kTREE23_UNKNOW_ERR;
 211	    }
 212
 213	public:
 214
 215	    void SetLeftSlot(Slot slot)
 216	    {
 217	        slot.Move2(m_leftSlot);
 218	    }
 219
 220	    void SetRightSlot(Slot slot)
 221	    {
 222	        slot.Move2(m_rightSlot);
 223	    }
 224
 225	    void SetSlot(Slot sl, Slot sr)
 226	    {
 227	        SetLeftSlot(sl);
 228	        SetRightSlot(sr);
 229	    }
 230
 231	    void Traversal()
 232	    {
 233	        subTreeTravesal(m_leftTree);
 234
 235	        m_leftSlot.Show();
 236
 237	        subTreeTravesal(m_midTree);
 238
 239	        if (isFullSlot())
 240	        {
 241	            m_rightSlot.Show();
 242	            subTreeTravesal(m_rightTree);
 243	        }
 244	    }
 245
 246	    // 要定义为private函数
 247	    void subTreeTravesal(SubTree subTree)
 248	    {
 249	        if (NULL != subTree )
 250	            subTree->Traversal();
 251	    }
 252
 253	public:
 254
 255	    // 父子关系是相互的
 256	    void SetTree(SubTree lt, SubTree mt, SubTree rt)
 257	    {
 258	        SetLeftTree(lt);
 259	        SetMidTree(mt);
 260	        SetRightTree(rt);
 261	    }
 262
 263	    void SetLeftTree(SubTree subTree)
 264	    {
 265	        // 父子关系是相互的
 266	        m_leftTree = subTree;
 267	        if( NULL != subTree )
 268	            subTree -> m_parent = this;
 269	    }
 270
 271	    void SetMidTree(SubTree subTree)
 272	    {
 273	        m_midTree = subTree;
 274	        if( NULL != subTree )
 275	            subTree -> m_parent = this;
 276	    }
 277
 278	    void SetRightTree(SubTree subTree)
 279	    {
 280	        m_rightTree = subTree;
 281	        if( NULL != subTree )
 282	            subTree -> m_parent = this;
 283	    }
 284
 285	    void SetParentTree(SubTree subTree)
 286	    {
 287	        m_parent = subTree;
 288	    }
 289
 290	public:
 291
 292	    void TreeAssert()
 293	    {
 294	        if(NULL != m_leftTree)
 295	            assert(m_leftTree->m_parent == this);
 296
 297	        if(NULL != m_midTree)
 298	            assert(m_midTree->m_parent == this);
 299
 300	        if(NULL != m_rightTree)
 301	            assert(m_rightTree->m_parent == this);
 302	    }
 303
 304	private:        // InsertNode 相关
 305
 306	    // 在当前节点上, 插入gUpNode:
 307	    // 命名"pUpNode"是因为这个节点是下面节点上升而来
 308	    // 内部操作有: 分裂节点, 递归向上继续插入分裂生成的节点.
 309	    // 最后返回最新的树根节点.
 310	    // 上升的节点, 肯定是一个oneSlot 节点
 311	    int InsertNode(Node *pUpNode, Tree &newRoot)
 312	    {
 313	        // 下面节点调用父节点插入上升节点, 父节点为空
 314	        if( NULL == this )
 315	        {
 316	            newRoot = pUpNode;
 317	            return kTREE23_SUC;
 318	        }
 319
 320	        if ( isEmptySlot() )
 321	            return Empty_InsertNode(pUpNode);
 322
 323	        if ( isOneSlot() )
 324	            return InPlace_InsertNode(pUpNode);
 325
 326	        else
 327	            // m_parent 可能为NULL(root节点的根节点为NULL), 可以在这里返回一个新的节点, 作为新的根.
 328	            return Split_InsertNode(pUpNode, newRoot);
 329
 330	        return  kTREE23_UNKNOW_ERR;
 331	    }
 332
 333
 334	    int Empty_InsertNode(Node *pUpNode)
 335	    {
 336	        Slot upSlot = pUpNode->m_leftSlot;
 337
 338	        SetLeftSlot(upSlot);
 339
 340	        SetTree(pUpNode->m_leftTree, m_midTree, NULL);
 341
 342	        delete pUpNode;        // 释放节点.
 343	        return kTREE23_SUC;
 344	    }
 345
 346	    // 在当前节点插入一个下面上升来的节点.(原地还有一个空槽)
 347	    // 上升节点分裂而来, 必定是一个oneSlot 节点
 348	    int InPlace_InsertNode(Node *pUpNode)
 349	    {
 350	        Slot upSlot = pUpNode->m_leftSlot;
 351
 352	        T  inPlaceEle = m_leftSlot.GetEle();
 353	        T  upEle      = upSlot.GetEle();
 354
 355	        if (upEle < inPlaceEle)
 356	        {
 357	            SetSlot(upSlot, m_leftSlot);
 358	            SetTree(pUpNode->m_leftTree, pUpNode->m_midTree, m_rightTree);
 359	        }
 360
 361	        if (upEle > inPlaceEle)
 362	        {
 363	            SetSlot(m_leftSlot, upSlot);
 364	            SetTree(m_leftTree, pUpNode->m_leftTree, pUpNode->m_midTree);
 365	        }
 366
 367	        delete  pUpNode;
 368	        return kTREE23_SUC;
 369	    }
 370
 371	    // 2-3树操作中最复杂的之处: 因为分裂的情况比较多
 372	    // 当前节点无空槽, 分裂当前节点, 插入新节点.
 373	    int Split_InsertNode(Node  *pUpNode, Tree &newRoot)
 374	    {
 375	        Slot upSlot = pUpNode->m_leftSlot;
 376
 377	        T  leftEle  = m_leftSlot.GetEle();
 378	        T  rightEle = m_rightSlot.GetEle();
 379	        T  upEle    = upSlot.GetEle();
 380
 381	        // 先将m_parent保存下来, 下面操作会修改m_parent的值
 382	        PNode originParent = this ->m_parent;
 383
 384	        PNode upSplit;
 385
 386	        if (upEle < leftEle)                             // 上升节点居左.
 387	            upSplit = leftSplit(pUpNode);
 388
 389	        if ( (upEle > leftEle) && (upEle < rightEle) )   // 上升节点居中.
 390	            upSplit = midSplit(pUpNode);
 391
 392	        if ( upEle > rightEle )                          // 上升节点居右.
 393	            upSplit = rightSplit(pUpNode);
 394
 395
 396	        // 最后, 将upSplit 交给父节点处理
 397	        return originParent -> InsertNode(upSplit, newRoot);
 398
 399	        //return Parent_InsertNode(upSplit, newRoot);
 400	    }
 401
 402
 403	    int Parent_InsertNode(Node *pUpNode, Tree &newRoot)
 404	    {
 405	        if ( NULL == m_parent )
 406	        {
 407	            newRoot = pUpNode;
 408	            return kTREE23_SUC;
 409	        }
 410
 411	        return m_parent->InsertNode(pUpNode, newRoot);
 412	    }
 413
 414
 415	private:        // split相关
 416
 417	    PNode leftSplit(Node  *pUpNode)
 418	    {
 419	        ExpNode  expNode;
 420
 421	        // 上升节点居左.
 422	        // 需重构, 分离出新函数.
 423	        Node  *leftSplit  = pUpNode;
 424	        Node  *upSplit    = new Node();
 425	        Node  *rightSplit = this;
 426
 427	        // 抛弃 this 的 m_leftTree: 被细化为 pUpNode 的 m_leftTree + m_midTree
 428	        expNode.Init( pUpNode -> m_leftTree,
 429	                      pUpNode -> m_midTree,
 430	                      this    -> m_midTree,
 431	                      this    -> m_rightTree,
 432
 433	                      pUpNode-> m_leftSlot,
 434	                      this   -> m_leftSlot,
 435	                      this   -> m_rightSlot
 436	                    );
 437
 438
 439	        expNode.Explode(leftSplit, upSplit, rightSplit);
 440	        return  upSplit;
 441	    }
 442
 443	    PNode midSplit(Node  *pUpNode)
 444	    {
 445	        ExpNode  expNode;
 446
 447	        Node *leftSplit  = this;
 448	        Node *upSplit    = pUpNode;
 449	        Node *rightSplit = new Node();
 450
 451	        // this的midTree被抛弃, 被细化成upSplit的m_leftTree + m_midTree
 452	        expNode.Init( this    -> m_leftTree,
 453	                      pUpNode -> m_leftTree,
 454	                      pUpNode -> m_midTree,
 455	                      this    -> m_rightTree,
 456
 457	                      this    -> m_leftSlot,
 458	                      pUpNode -> m_leftSlot,
 459	                      this    -> m_rightSlot
 460	                    );
 461
 462	        expNode.Explode(leftSplit, upSplit, rightSplit);
 463	        return upSplit;
 464	    }
 465
 466	    PNode rightSplit(Node  *pUpNode)
 467	    {
 468	        ExpNode  expNode;
 469	        Node *leftSplit  = this;
 470	        Node *upSplit    = new Node();
 471	        Node *rightSplit = pUpNode;
 472
 473	        // this的m_rightTree被抛弃, 被细化成upSplit的m_leftTree + m_midTree
 474	        expNode.Init( this    -> m_leftTree,
 475	                      this    -> m_midTree,
 476	                      pUpNode -> m_leftTree,
 477	                      pUpNode -> m_midTree,
 478
 479	                      this    -> m_leftSlot,
 480	                      this    -> m_rightSlot,
 481	                      pUpNode -> m_leftSlot
 482	                    );
 483
 484	        expNode.Explode(leftSplit, upSplit, rightSplit);
 485	        return upSplit;
 486	    }
 487
 488
 489	private:    // find 相关
 490
 491	    bool leftFind(T ele, PNode &findNode)
 492	    {
 493	        if ( NULL == m_leftTree )
 494	            return false;
 495
 496	        return m_leftTree->Find(ele, findNode);
 497	    }
 498
 499	    bool rightFind(T ele, PNode &findNode)
 500	    {
 501	        if ( NULL == m_rightTree )
 502	            return false;
 503
 504	        return m_rightTree->Find(ele, findNode);
 505	    }
 506
 507	    bool midFind(T ele, PNode &findNode)
 508	    {
 509	        if ( NULL == m_midTree )
 510	            return false;
 511
 512	        return m_midTree->Find(ele, findNode);
 513	    }
 514
 515
 516	private:    // 判断 + 初始化
 517
 518	    // 两个slot全空
 519	    bool isEmptySlot() {
 520	        return  m_leftSlot.IsEmpty() && m_rightSlot.IsEmpty();
 521	    }
 522
 523	    // 一个slot空, 还有一个slot满.(本代码中是leftSlot已用, rightSlot未用)
 524	    bool isOneSlot() {
 525	        // 既不全空, 也不全满
 526	        return  !( isFullSlot() ||
 527	                   isEmptySlot() );
 528	    }
 529
 530	    // 两个slot全满
 531	    bool isFullSlot() {
 532	        return    !( m_leftSlot.IsEmpty() ||
 533	                     m_rightSlot.IsEmpty() );
 534	    }
 535
 536	    void initResource()
 537	    {
 538	        m_parent    = NULL;
 539	        m_leftTree  = NULL;
 540	        m_midTree   = NULL;
 541	        m_rightTree = NULL;
 542	    }
 543
 544	};
 545
 546	// 爆炸节点, 即一个3节点: 即将被分裂
 547	template <class T>
 548	class  ExplodeNode
 549	{
 550	public:
 551	    typedef Tree23_Node<T>   *Tree;         // 用 Tree23_Node指针类型表示2-3 树.
 552	    typedef Tree23_Node<T>    Node;         // 用 Tree23_Node指针类型表示2-3 树.
 553	    typedef Tree23_Slot<T>    Slot;
 554
 555	public:
 556	    ExplodeNode() {
 557	        //memset(m_mergeTree, 0, sizeof(Tree) * 4);    // m_mergeTree = {NULL};
 558	        memset(m_mergeTree, 0, sizeof(m_mergeTree));    // m_mergeTree = {NULL};
 559	    }
 560
 561	    void Init(Tree t0, Tree t1, Tree t2, Tree t3,
 562	              Slot &ls, Slot &ms, Slot &rs
 563	            )
 564	    {
 565	        m_mergeTree[0] = t0;
 566	        m_mergeTree[1] = t1;
 567	        m_mergeTree[2] = t2;
 568	        m_mergeTree[3] = t3;
 569
 570	        ls.Move2(m_leftSlot );
 571	        ms.Move2(m_midSlot  );
 572	        rs.Move2(m_rightSlot);
 573	    }
 574
 575	    // 开始爆炸吧: 轰, 数据就分裂到了 左 + 右 + 上节点
 576	    void Explode(Node *leftSplit, Node *upSplit, Node *rightSplit)
 577	    {
 578	        // slot re assign
 579	        leftSplit  -> SetLeftSlot(m_leftSlot);
 580	        upSplit    -> SetLeftSlot(m_midSlot);
 581	        rightSplit -> SetLeftSlot(m_rightSlot);
 582
 583	        // subtree re assign
 584	        leftSplit  -> SetTree(m_mergeTree[0], m_mergeTree[1], NULL);
 585	        rightSplit -> SetTree(m_mergeTree[2], m_mergeTree[3], NULL);
 586	        upSplit    -> SetTree(leftSplit     , rightSplit    , NULL);
 587	    }
 588
 589	    // 3 节点上有4棵树, 3个slot
 590	    Tree  m_mergeTree[4];
 591	    Slot  m_leftSlot;
 592	    Slot  m_midSlot;
 593	    Slot  m_rightSlot;
 594	};
 595
 596
 597	template <class T>
 598	class  Tree23_Slot
 599	{
 600	    typedef Tree23_Slot<T>  Slot;
 601
 602	private:
 603	    T       m_ele;          // 元素本身
 604	    bool    m_empty;        // 元素是否可用( 因为没有办法通过节点的子树, 或者元素本身的值判定槽中是否存入了元素.)
 605
 606	public:
 607	    Tree23_Slot() {
 608	        m_empty = true;
 609	    }
 610
 611	    Tree23_Slot(T ele) {
 612	        m_ele   = ele;
 613	        m_empty = false;
 614	    }
 615
 616	    void Show()
 617	    {
 618	        std::cout << m_ele << std::endl;
 619	    }
 620
 621	    void SetEle(T ele) {
 622	        m_ele = ele;
 623	        setFull();
 624	    }
 625
 626	    // copy后, invalidate 当前slot
 627	    void Move2(Slot &to) {
 628	        if (this == &to)    // 避免了同一个对象Move2, 导致setEmpty()的情况.
 629	            return;
 630
 631	        Copy2(to);
 632	        setEmpty();
 633	    }
 634
 635	    // Copy, 就是copy构造函数的功能: 但还是写出来, 和Copy2 相对应.
 636	    void Copy2(Slot &to) const {
 637	        to = *this;
 638	    }
 639
 640	    bool IsEquel(T ele) {
 641	        return ele == m_ele;
 642	    }
 643
 644	    bool IsEmpty() const { return m_empty; }
 645	    T&   GetEle()  { return m_ele; }
 646
 647	private:
 648
 649	    void setEmpty()   { m_empty = true;  }
 650	    void setFull()    { m_empty = false; }
 651	};
 652
 653	#endif   /* ----- #ifndef tree23_H_  ----- */
